package com.cloud.code.算法.斐波拉契数列;

import java.util.HashMap;
import java.util.Map;

/**
 * 这里使用了动态规划的思想， 把已经计算过的结果缓存起来。
 */
public class Test {

    public static void main(String[] args) {
        int n = 5;
        Map<Integer,Integer> map = new HashMap<>();
        int sum = sum(n,map);

        System.out.println(sum);

    }

    private static int sum(int n,Map<Integer,Integer> map) {

        if(n == 1 || n == 2){
            System.out.println("-----------11");
            return 1;
        }
        Integer integer = map.get(n);
        if(integer == null){
            int sum = sum(n - 1, map) + sum(n - 2, map);
            map.put(n,sum);
            System.out.println(n);
            System.out.println(sum);
            System.out.println("--------");
            return sum;
        }else {
            return integer;
        }

    }


}
